﻿//#define _CRT_SECURE_NO_WARNINGS 1
//
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
////int main()
////{
////	char str[50] = { 0 };
////
////	fgets(str, 10, stdin);
////
////	printf("%s\n", str);
////	return 0;
////}
//
////#include<string.h>
////int main()
////{
////	char str1[50] = "This is str1";
////	char str2[50] = "This is str2";
////
////	strncat(str1, str2, 15);
////
////	printf("最终的目标字符串：%s", str1);
////	system("pause");
////	return 0;
////}
//
//
////给你一个 升序排列 的数组 nums ，请你 原地 删除重复出现的元素，
////使每个元素只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。
////
////由于在某些语言中不能改变数组的长度，所以必须将结果放在数组nums的第一部分。
////更规范地说，如果在删除重复项之后有 k 个元素，那么 nums 的前 k 个元素应该保存最终结果。
//
////快慢指针
////int removeDuplicates(int* nums, int numsize)
////{
////	if (numsize == 0)
////		return 0;
////	int fast = 1;
////	int slow = 1;
////	while (fast < numsize)
////	{
////		if (nums[fast] != nums[fast-1])
////		{
////			nums[slow] = nums[fast];
////			++slow;
////		}
////		++fast;
////	}
////	return slow;
////}
////int main()
////{
////	int nums[] = { 0,0,1,1,1,2,2,2,3,3,4 };
////	int sz = sizeof(nums) / sizeof(nums[0]);
////	int ret = removeDuplicates(nums, sz);
////	for (int i = 0; i < ret; i++)
////	{
////		printf("%d ", nums[i]);
////	}
////	system("pause");
////}
//
typedef int STDataType;
// 支持动态增长的栈
struct Stack
{
	STDataType* a;
	STDataType top; //栈顶
	int capacity;  //栈的容量
};

typedef struct Stack ST;

//初始化栈
void STinit(ST** ps);

//入栈
void STPush(ST* ps, STDataType x);

//出栈
void StackPop(ST* ps);

// 获取栈顶元素
STDataType StackTop(ST* ps);

// 获取栈中有效元素个数
int STSize(ST* ps);


// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 
bool STEmpty(ST* ps);


// 销毁栈
void STDestroy(ST* ps);

//初始化栈
void STinit(ST** ps)
{
	*ps = (ST*)malloc(sizeof(ST));
	if (ps== NULL)
	{
		perror("err:");
		exit(-1);
	}
	(*ps)->a = (STDataType*)malloc(sizeof(STDataType) * 4);
	if ((*ps)->a == NULL)
	{
		perror("err:");
		exit(-1);
	}
	else
	{
		(*ps)->top = 0;
		(*ps)->capacity = 4;
	}
	
}

//入栈
void STPush(ST* ps, STDataType x)
{
	assert(ps);
	//是否需要增容
	if (ps->top == ps->capacity)
	{
		STDataType* tmp = realloc(ps->a, ps->capacity * 2 * sizeof(STDataType));
		if (tmp == NULL)
		{
			perror("err");
		}
		else
		{
			ps->a = tmp;
			ps->capacity *= 2;
		}
	}
	ps->a[ps->top] = x;
	ps->top++;
}

//出栈
void StackPop(ST* ps)
{
	assert(ps);
	assert(ps->top > 0);
	ps->top--;
}

//获得栈顶元素
STDataType StackTop(ST* ps)
{
	assert(ps);
	return ps->a[ps->top - 1];
}


int STSize(ST* ps)
{
	assert(ps);
	return ps->top;
}

// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 
bool STEmpty(ST* ps)
{
	assert(ps);
	/*if (ps->top == 0)
		return -1;
	else
		return 0;*/
	return ps->top == 0;
}

// 销毁栈
void STDestroy(ST* ps)
{
	free(ps->a);
	ps->a = NULL;
	ps->top = ps->capacity = 0;
}


typedef struct {
	ST* q1;
	ST* q2;
} MyQueue;

//先获得一个队列
MyQueue* myQueueCreate() {
	MyQueue* SQ = (MyQueue*)malloc(sizeof(MyQueue));
	if (SQ == NULL)
	{
		assert(SQ);
	}
	//SQ->q1 = SQ->q2 = NULL;
	STinit(&SQ->q1);
	STinit(&SQ->q2);
	return SQ;
}

void myQueuePush(MyQueue* obj, int x) {
	assert(obj);
	STPush(obj->q1, x);
}

int myQueuePop(MyQueue* obj) {
	assert(obj);
	int ret = 0;
	if (!STEmpty(obj->q2))
	{
		ret = StackTop(obj->q2);
		StackPop(obj->q2);
	}
	else
	{
		while (!STEmpty(obj->q1))
		{
			STPush(obj->q2, StackTop(obj->q1));
			StackPop(obj->q1);
		}
		ret = StackTop(obj->q2);
		StackPop(obj->q2);
	}
	return ret;
}

int myQueuePeek(MyQueue* obj) {
	assert(obj);
	int head = 0;
	if (!STEmpty(obj->q2))
	{
		head = StackTop(obj->q2);
	}
	else
	{
			while (!STEmpty(obj->q1))
			{
				STPush(obj->q2, StackTop(obj->q1));
				StackPop(obj->q1);
			}
			head = StackTop(obj->q2);
			//StackPop(obj->q2);
	}
	
	return head;
}

bool myQueueEmpty(MyQueue* obj) {
	return STEmpty(obj->q1) && STEmpty(obj->q2);
}

void myQueueFree(MyQueue* obj) {
	free(obj->q1);
	free(obj->q2);
	/*obj->q1->top = 0;
	obj->q1->capacity = 0;
	obj->q2->top = 0;
	obj->q2->capacity = 0;
	obj->q1 = obj->q2 = NULL;*/
	free(obj);
	obj = NULL;
}


void test()
{
	MyQueue* obj = myQueueCreate();
	myQueuePush(obj, 1);
	myQueuePush(obj, 2);
	int pos = myQueuePeek(obj);
	printf("%d\n", pos);
	int ret = myQueuePop(obj);
	printf("%d\n", ret);
	/*if (myQueueEmpty(obj) == true)
	{
		printf(" falst\n ");
	}
	else
	{
		printf(" ture \n");
	}*/
	printf("%d\n", myQueueEmpty(obj));
}
int main()
{
	test();
	system("pause");
}
// 
// 
//#include<stdio.h>
//#include<stdlib.h>
//#include<assert.h>
//#include<stdbool.h>
//#include "Queue.h"
//typedef char BTDataType;
//
//struct BinarytreeNode
//{
//	struct BinarytreeNode* left;
//	struct BinarytreeNode* right;
//	BTDataType Data;
//};
//
//typedef struct BinarytreeNode BTNode;
//
////前序(先根): 根=左子树-右子树
//void preorder(BTNode* root)
//{
//	if (root == NULL)
//	{
//		printf("NULL ");
//		return;
//	}
//	printf("%c ", root->Data);
//	preorder(root->left);
//	preorder(root->right);
//}
//
//
////中序(中根) : 左子树 - 根 - 右子树
//void Middleorder(BTNode* root)
//{
//	if (root == NULL)
//	{
//		printf("NULL ");
//		return;
//	}
//	Middleorder(root->left);
//	printf("%c ", root->Data);
//	Middleorder(root->right);
//}
//
////后序(后序): 左子树 右子树 根
//void afterorder(BTNode* root)
//{
//	if (root == NULL)
//	{
//		printf("NULL ");
//		return;
//	}
//	afterorder(root->left);
//	afterorder(root->right);
//	printf("%c ", root->Data);
//}
//
////有几个节点度
//int TreeSize(BTNode* root)
//{
//	return root == NULL ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1;
//}
//
////有几个叶节点叶度为0的
//int TreeleafSize(BTNode* root)
//{
//	if (root->left == NULL && root->right == NULL)
//	{
//		return 1;
//	}
//		return TreeleafSize(root->left)+TreeleafSize(root->right);
//}
//
////层序遍历广度优先遍历
////队列 先进先出
////核心思路就是 : 上一层带下一层
//void leve10rder(BTNode* root)
//{
//	assert(root);
//	//要的是一个队列
//	Queue q;
//	QueueInit(&q);
//	//先进一个元素
//	QueuePush(&q, root);
//	while (!QueueEmpty(&q))
//	{
//		BTNode* pos = QueueFront(&q);
//		printf("%c ", pos->Data);
//		QueuePop(&q);
//		if (pos->left != NULL && pos->right != NULL)
//		{
//			QueuePush(&q, pos->left);
//			QueuePush(&q, pos->right);
//		}
//	}
//	printf("\n");
//
//	QueueDestroy(&q);
//}
//
//int main()
//{
//	BTNode* A = (BTNode*)malloc(sizeof(BTNode));
//	A->Data = 'A';
//	A->left = NULL;
//	A->right = NULL;
//
//	BTNode* B = (BTNode*)malloc(sizeof(BTNode));
//	B->Data = 'B';
//	B->left = NULL;
//	B->right = NULL;
//
//
//	BTNode* C = (BTNode*)malloc(sizeof(BTNode));
//	C->Data = 'C';
//	C->left = NULL;
//	C->right = NULL;
//
//
//	BTNode* D = (BTNode*)malloc(sizeof(BTNode));
//	D->Data = 'D';
//	D->left = NULL;
//	D->right = NULL;
//
//
//	BTNode* E = (BTNode*)malloc(sizeof(BTNode));
//	E->Data = 'E';
//	E->left = NULL;
//	E->right = NULL;
//
//	A->left = B;
//	A->right = C;
//	B->left = D;
//	B->right = E;
//
//	//afterorder(A);
//	
//	/*int pos = TreeSize(A);
//	printf("%d\n", pos);*/
//
//	/*int pos = TreeleafSize(A);
//	printf("%d\n", pos);*/
//
//	leve10rder(A);
//	system("pause");
//}